The present invention relates to a Viterbi decoding device and a Viterbi decoding method, and more particularly relates to a Viterbi decoding apparatus and Viterbi decoding method of actually performing high-speed Viterbi decoding in a form of traceback where reading out and writing of survivor sequences information is carried out alternately at two path memories.
Data signals transmission has been carried out with the data signal being coded for the purpose of making errors correctable which are due to noise occurring in the data transmission process.
FIG. 1 shows the configuration of an example of a coding apparatus 1 for carrying out convolutional coding of a constraint length of 3 and a coding rate of 1/2.
The coding apparatus 1 comprises a three-bit shift register comprising registers R1, R2 and R3 together with two exclusive OR circuits (exclusive OR circuit E1 and exclusive OR circuit E2).
The exclusive OR circuit E1 carries out an exclusive OR operation on the information bits of registers R1, R2 and R3 and outputs the result as value X1. The exclusive OR circuit E2 then performs an exclusive OR operation on the information bits for registers R1 and R3 and outputs the result as the value X2.
When one bit of information is inputted to the register R1, the information bit stored in the register R1 is shifted to the register R2 and the information bit stored in the register R2 is shifted to register R3.
When the value of the information bit stored in the register R1 is a and the value of the information bit stored in the register R2 is b, suppose that one bit of information In is inputted to the register R1 and a value X1 and a value X2 are outputted.
The value of the information bits stored in registers R1, R2 and R3 at this time are the values of the inputted information bit In, the values a and b, respectively. Then, the number of states for the coding apparatus 1 at the time the one bit of information is inputted is therefore decided by the combination (a, b). Namely, in this case, there exist four states (0, 0), (0, 1), (1, 0) and (1, 1). Generally, the number of states when the number of registers is n (the constraint length is n) can be expressed by 2 (n-1) (where indicates that the following number is an exponent).
FIG. 2 is a trellis line diagram corresponding to the coding apparatus 1.
In FIG. 2, the states that can be obtained at the coding apparatus 1 are shown as the states 0 to 3, with the values X1 and X2 outputted in accordance with the information bits inputted at the time of each of these states being shown as (X1, X2). Here, the state transitions when 0 is inputted as the information bit are shown by solid lines and state transitions when 1 is inputted are shown as dotted lines.
For example, when the state is 0 (a=b=0), for 0 being inputted as an information bit, (00) (X1=0 and X2=0) are outputted and a transition is made to state 0 (the state does not change). Further, when the state is 0 (a=b=0) and 1 is inputted as an information bit, (11) (X1=1 and X2=1) are outputted and a transition is made to state 1.
The data thus coded has a superior random error correction performance. For example, highly reliable data can be obtained by using Viterbi decoding for deciding the most probable path and converting the coded data to decoded data.
A more specific example of Viterbi decoding is described with reference to FIG. 3 and FIG. 4.
When the state of the coding apparatus 1 is in the state of 0 (a=b=0) as an initial value, information bits are taken as being inputted to the encoding device 1 in the order of (0, 1, 0, 0). Directly after this, data (0, 0) signifying the end of the input data is inputted to the coding apparatus 1. Namely, in this case, data is inputted to the coding apparatus 1 in the order of (0, 1, 0, 0, 0, 0) and the coded data (00, 11, 10, 11, 00, 00) is outputted for this input.
Suppose that errors occur at the second and fifth bits with regards to this coded data, with the result that data (01, 11, 00, 11, 00, 00) is transmitted.
FIG. 3 shows a trellis line diagram up to the third block of this data.
In the Viterbi decoding, when (01) is transmitted at the first clock in (stage 0, state 0), a path metric is calculated after obtaining a branch metric showing a degree of probable transition to (stage 1, state 0) or (stage 1, state 1) to which transition is possible from this (stage 0, state 0). More specifically, these processes are carried out by calculating Hamming distances showing the sum of the differences in comparing the code word in every path ((00) and (11)) and the actual code word (01) for each of the components.
In this case, the branch metric for the path from (stage 0, state 0) to (stage 1, state 0) is 1 because the Hamming distance is 1 (because the comparison of the code word (00) and the actual code word (01) shows no difference for the first bit and the difference of 1 for the second bit, then 0+1=1). Similarly, a branch metric obtained for the path from (stage 0, state 0) to (stage 1, state 1) becomes 1 (=1+0). This and that the path metric for (stage 0, state 0) is also 0 make the path metrics for both (stage 1, state 0) and (stage 1, state 1) as being 1 (=0+1).
Next, when (11) is transmitted at the second clock, a path metric is obtained which is for the transition from each of the states ((stage 1, state 0) and (stage 1, state 1)) to states to which transitions are possible. That is because the branch metric from (stage 1, state 0) to (stage 2, state 0) is 2 (=1+1) and the path metric for (stage 1, state 0) is therefore 1, the path metric for (stage 2, state 0) is 3 (=1+2). The path metrics for (stage 2, state 1), (stage 2, state 2) and (stage 2, state 3) are therefore 1, 2 and 2.
Next, when (00) is transmitted at the third clock, a path metric is obtained for each of the states of the third stage but transitions from two states can be considered at each of the states of the third stage. In this case, a path having a smaller path metric is made to be selected. For example, at (stage 3, state 0), paths from (stage 2, state 0) and from (stage 2, state 2) exist. However, a path metric calculation about the path from (stage 2, state 0) gives 3 and a path metric obtained about the path from (stage 2, state 2) becomes 4. The path from (stage 2, state 0) is therefore selected as the survivor sequence.
Thus obtained survivor sequences with respect to code words up to the sixth clock are shown in FIG. 4.
In FIG. 4, two paths (00, 00, 00, 00, 00, 00) and (00, 11, 10, 11, 00, 00) are shown as survivor sequences (the final state always becomes 0 because (0,0) indicating the end of the data is given as the input data). Here, Hamming distances are then obtained for each of the code string of these two paths and the actual code string, with the smaller one of these paths being selected. Namely, (00, 11, 10, 11, 00, 00) is selected as the final survivor sequence because the Hamming distance for (00, 00, 00, 00, 00, 00) and (01, 11, 00, 11, 00, 00) is 5 and the Hamming distance for (00, 11, 10, 11, 00, 00) and (01, 11, 00, 11, 00, 00) is 2. The code string is the same as the output data of the coding apparatus 1 and is a code string with errors being removed.
In this way, errors included in transmitted coded data can be corrected.
For actually carrying out Viterbi decoding, such a path memory is necessary as that for storing survivor sequences having a configuration corresponding to, for example, the trellis line diagram shown in FIG. 2.
In the aforementioned example, a description was given of the case of a short code string (00, 11, 10, 11, 00, 00), but code strings are generally quite long. Therefore, when Viterbi decoding is exactly carried out it is necessary to store survivor sequences up until the end of the code string. However, in this case, the number of memory cells increases tremendously and the delay time for decoding also becomes excessive. Then, the newest path of a prescribed length is usually stored in the path memory, and the decode word data occurring at the time of inputting the oldest path is decided upon and outputted directly before writing a new path and the oldest path is then discarded.
Further, there are two decoding methods for carrying out Viterbi decoding using survivor path information stored in the path memory, the traceback method (see Japanese Laid-Open Patent Publication 62-23933) and the RE (Register Exchange) method (see IEEE Transactions on Communications, vol. 41, No. 3 (March, 1993)). The RE method consumes larger power when compared with the traceback method, but has higher decoding speed. The RE method is therefore used in order to carry out decoding at high speeds.
However, in the case of convolution coded data of a constraint length of 7, the number of states becomes as much as 64 and a large number of gates is necessary for path memory using the RE method. As a result, the power consumed in CMOS LSIs comprising the gates therefore becomes large and the resulting heat generation becomes excessive. This causes a problem that the CMOS LSIs cannot be put into a plastic package when an attempt is made to fabricate the path memory as an IC.
Then, it can be considered to use the less power consuming form of traceback by making its decoding speed high. For example, the RAM for storing the survivor sequences can be partitioned into a plurality of memory banks for carrying out the writing of survivor sequence information and decoding (reading out) using traceback in parallel with separate memory banks.
However, even in this case, the decoding speed is not sufficient and it is difficult to achieve higher-speed decoding using the traceback method.
As the present invention sets out to resolve the aforementioned problems, it is the object of the present invention to realize a Viterbi decoding device that carries out decoding at a high speed by carrying out an interleave operation with respect to two RAMs.